The present invention relates generally to memory devices and particularly to dual port first-in-first-out (FIFO) memory devices. More particularly, the present invention relates to detecting faults in dual port FIFO memory devices.
Fast, efficient testing is an important step in manufacturing memory chips, and the price paid for recent advances in semiconductor technology has been a lengthier and more complicated testing process. Consequently, procedures that test the memory thoroughly, quickly, and without complication are highly prized. One type of memory chip is the first-in-first-out (FIFO) memory, commonly referred to simply as a xe2x80x9cFIFO.xe2x80x9d Like conventional memories, a FIFO performs read operations, which retrieve data from the FIFO, as well as write operations, which store data in the FIFO. Unlike conventional memories which permit read and write operations in any desired order at specified memory locations, the FIFO reads out data in the same order the data was written. Suppose, for example, that a first data value is written to the FIFO, followed by a second data value and then a third data value. The first read operation performed on the FIFO will return the first data value. If a second read operation is performed, then the FIFO will retrieve the second data value, and if a third read operation is performed, the FIFO will retrieve the third data value. After the third and final data value is read from the FIFO, no more read operations can occur until another value is written to the FIFO, and thus the FIFO is said to be xe2x80x9cempty.xe2x80x9d The FIFO also may become full if all of the memory locations are written without reading any data. When full, the FIFO prohibits write operations, so data must first be read out of the FIFO to make room for further write operations.
A common feature of current memories, including many FIFO""s, is the presence of multiple xe2x80x9cports,xe2x80x9d or gateways that allow data to be read from and/or written to the memory. The ports on a multiport memory are designed to function independently, allowing memory accesses to multiple locations at the same time. Prior memories, which had a single memory port, could only read or write data in one memory location at a time. Multiple ports thus increase memory throughput, or the speed at which data can be transferred to and from memory. FIFO""s often include two ports: one port that writes data, and one port that reads data. Accordingly, data values can be read and written concurrently.
FIG. 1 illustrates a representative multiport memory device 150, comprising an array of memory cells 100, 101, 109, 110, 111, 119, 190, 191 and 199. As shown in FIG. 1, the cells are organized into R rows and C columns, where R and C can be any values. Cells 100 and 101 represent the first two columns of the first row, and cell 109 represents the last (or Cxe2x88x921th) column of the first row. Similarly, cells 110, 111, and 119 represent the first, second, and last columns of the second row. In the final (or Rxe2x88x921th) row, cells 190, 191, and 199 occupy the first, second, and last columns, respectively. Each memory cell is capable of storing an electric charge, and the charges can be manipulated to store and recall data through the use of special control circuitry (not shown) in the memory 150. Each memory cell can represent one of two values, depending on whether or not the cell holds a charge. The values 1 and 0 are often used to represent the charged and uncharged states, respectively, although the reverse may be true. Because the cells can hold either of two possible values, the memory device 150 is called a xe2x80x9cbinaryxe2x80x9d device, and the cell data values are known as binary digits, or xe2x80x9cbits.xe2x80x9d
To fetch and store the data values, the memory device 150 includes signals known as xe2x80x9cword linesxe2x80x9d and xe2x80x9cbit linesxe2x80x9d that couple to the cells. The word lines connect cells in the same row and are used to activate the cells along one row at a time. The bit lines connect cells in the same column and are used to carry data to and from the activated cells. In a multiport device, each port has its own word lines and bit lines. The memory device 150 in FIG. 1 is shown with P ports, where P can be any number but is typically less than or equal to 11 under current technology.
The first port includes a first word line W10 that connects the cells 100, 101, and 109 in the first row; a second word line W11 that connects the cells 110, 111, and 119 in the second row; and additional word lines for the other rows, including a word line WP(Rxe2x88x921) that connects the cells 190, 191, and 199 in the final row. The first port also comprises a first bit line B10 that connects the cells 100, 110, and 190 in the first column; a second bit line B11 that connects the cells 101, 111, and 191 in the second column; and additional bit lines for the remaining columns, including a bit line Bp(Cxe2x88x921) that connects the cells 109, 119, and 199 in the final column. To read data from the first row of cells through the first port, for example, the word line W10 is activated. In response to activating the word line W10, cells 100 and 101 place their data values onto bit lines B10 and B11, respectively. Similarly, the other cells in the first row drive their bit lines on the first port with the stored data, including cell 109, which drives bit line B1(Cxe2x88x921) with the data value stored in cell 109.
The word lines and bit lines also can be used to store data in the cells. To write data to the cells in the second row through the first port, for example, the word line W11 is asserted to activate the cells in the second row, including cells 110, 111, and 119. At the same time, the values being stored are placed on the bit lines belonging to the first port, including bit lines B10, B11, and B1(Cxe2x88x921). In response, the cells on the second row store the data encoded by the bit lines. Cell 110 thus stores the value of bit line B10, cell 111 stores the value of bit line B11, and cell 119 stores the value of bit line B1(Cxe2x88x921).
Similarly, the remaining ports include word lines and bit lines for accessing the memory cells. Ideally, one port can access any row of cells while another port is accessing another row of cells without interference between the two ports, since the ports do not share word lines and bit lines.
FIG. 2 illustrates a representative dual port FIFO memory 250 comprising an array of memory cells 230 which are interfaced via a write bus, a read bus, a write enable line, and a read enable line. The FIFO 250 comprises two ports: a read-only port and a write-only port. Accordingly, the FIFO 250 can execute a read and a write operation in parallel. The memory cells 230 are arranged in words of four bits each, although each word may comprise any number of bits. Memory cells 200-203 represent the lowest address in the array, followed by the memory word formed by cells 210-213 and then the memory word formed by cells 220-223. Memory cells 280-283 form the next to last memory word, while memory cells 290-293 form the final memory word. Letting N represent the total number of memory words in the array 230, cells 200-203 represent the 0th word (or xe2x80x9caddress 0xe2x80x9d), and cells 290-293 represent the Nxe2x88x921th word (or xe2x80x9caddress Nxe2x88x921xe2x80x9d). The FIFO 250 also includes a full flag 252 which is set to logic 1 if the FIFO 250 becomes full, and an empty flag 256 which is set to logic 1 if the FIFO 250 is empty. To perform a read operation, the read enable line must be asserted. If a read operation is initiated, or attempted, when the read enable line is deasserted, then the FIFO will not perform the read operation. Similarly, if a write operation is initiated when the write enable line is not asserted, the FIFO will not perform the write operation. The write enable line must be asserted in order to write values to the FIFO 250.
Each word in the FIFO 250 receives a write word line, which activates the word during write operations, and a read word line, which activates the word during read operations. As shown in FIG. 2, Memory word 0 (cells 200-203) couples to write word line WW0 and to read word line RW0, memory word 1 (cells 210-213) receives write word line WW1 and read word line RW1, memory word 2 (cells 220-223) receives write word line WW2 and read word line RW2, memory word Nxe2x88x922 (cells 280-283) receives write word line WW8 and read word line RW8, and memory word Nxe2x88x921 receives write word line WW9 and read word line RW9. Similarly, each column of cells couples to a common bit line on each port. The cells forming the 0th column of the array 230 (including cells 200, 210, 220, 280, and 290) couple to write bit line WB0 and to read bit line RB0, and the cells that form the 1st column (e.g., cells 201, 211, 221, 281, and 291) couple to write bit line WB1 and to read bit line RB1. Likewise, the cells forming the 2nd column (e.g., cells 202, 212, 222, 282, and 292) couple to write bit line WB2 and to read bit line RB2, while the cells that form the 3rd column (e.g., cells 203, 213, 223, 283, and 293) couple to write bit line WB3 and read bit line RB3. Accordingly, write bit lines WB0-WB3 form a write bus, and read bit lines RB0-RB3 form a read bus.
A write shift register 232A selects one memory word to be activated on the write port, subject to the values of the write enable line and the full flag 252. The write shift register 232A comprises a series of cascaded register bits 240A-249A, each bit corresponding to one word of the array 230. Register bit 240A, when asserted, selects the 0th memory word, for example, while register bits 241A and 242A, when asserted, select the 1st and 2nd memory words, respectively. Similarly, register bits 248A and 249A correspond to memory words Nxe2x88x922 and Nxe2x88x921, respectively. So that only one word at a time may be selected for write operation, exactly one of the register bits is assigned logic 1 at any given moment. The remaining register bits are cleared to logic 0. The logic 1 value is known as the xe2x80x9cwrite pointer,xe2x80x9d since it indicates which cell will receive the next write operation. To begin FIFO operation, for example, the write pointer is located in the 0th register bit 240A by setting bit 240A to logic 1. The remaining register bits 241A-249A are cleared to logic 0""s. Following each write operation, the write pointer is transferred to the next register bit, and the register that held the pointer during the write operation is cleared. Note that the final register bit 249A feeds the initial register bit 240A, so that the write pointer scrolls over to the initial register bit 240A after a write operation occurs at the Nxe2x88x921th memory word.
The full flag 252 and write enable line are combined in an AND gate 254, which activates if the write enable line is asserted and the full flag 252 is deasserted. Each register bit drives a corresponding AND gate which also receives the output signal from AND gate 254. As shown in FIG. 2, AND gates 260A, 261A, and 262A drive write word lines WW0, WW1, and WW2, respectively, while AND gates 268A and 269A drive write word lines WW8 and WW9. Further, register bits 240A, 241A, and 242A drive AND gates 260A, 261A, and 262A, while register bits 248A and 249A drive AND gates 268A and 269A. Accordingly, a given write word line can only become asserted if the write enable line is asserted, if the full flag 252 is deasserted, and if the corresponding register bit is asserted.
A read shift register 232B selects one memory word to be activated on the read port, subject to the values of the read enable line and the empty flag 256. The read shift register 232B comprises substantially the same architecture as the write shift register 232A, including cascaded bits 240B-249B, with bit 249B feeding bit 240B. Each bit corresponds to one memory word. Bits 240B, 241B, and 242B correspond to memory words 0, 1, and 2, for example, while bits 248B and 249B correspond to memory words Nxe2x88x922 and Nxe2x88x921, respectively. Exactly one of the register bits holds a logic 1-valued xe2x80x9cread pointerxe2x80x9d that indicates which word will be activated for the next read operation. Following each read operation, the read pointer is transferred to the next bit in the register, and the register that held the read pointer during the read operation is cleared to logic 0.
Because the FIFO 250 includes shift registers that carry the read and write pointers, the FIFO of FIG. 2 is commonly known as a pointer-based FIFO. Another type of FIFO, known as a counter-based FIFO, incorporates read and write counters which store the addresses of the read and write locations, respectively. Each counter feeds a decoder, which activates the appropriate word line based on the value of the counter. The read counter increments the read address after each read operation, and the write counter increments the write address after each write operation, thus advancing the read and/or write locations. The counter-based FIFO and pointer-based FIFO thus perform the same function, albeit with slightly different logic structures.
The empty flag 256 and read enable line feed an AND gate 258, which asserts its output line high if the read enable line is asserted and the empty flag 256 is deasserted. Each register bit drives a corresponding AND gate which also receives the output signal from AND gate 258. As shown in FIG. 2, AND gates 260B, 261B, and 262B drive read word lines RW0, RW1, and RW2, respectively, while AND gates 268B and 269B drive read word lines RW8 and RW9. Further, register bits 240B, 241B, and 242B drive AND gates 260B, 261B, and 262B, while register bits 248B and 249B drive AND gates 268B and 269B. Accordingly, a given read word line is asserted only if the read enable line is asserted, if the empty flag 256 is deasserted, and if the pointer is in the corresponding register bit.
In addition to reading and writing data, some FIFO""s are capable of manipulating the read and write pointers through reset and retransmit commands. The retransmit command resets the fit read pointer to address 0 of the FIFO, corresponding to register 240B in FIG. 2. Setting the read pointer back to address 0 permits reading the memory words between address 0 and the location of the write pointer. The retransmit command may be used, for example, if the data from a series of read operations becomes garbled in route to its destination. By setting back the read pointer, the retransmit command permits rereading the data. Another command, the reset command, resets both the read pointer and the write pointer to address 0. Thus, the write pointer moves to register bit 240A in response to the reset command, and the read pointer moves to register bit 240B. Note that in some FIFO""s, the retransmit command may move the read pointer to the location of the write pointer, although this feature varies among different types of FIFO""s.
Although multiport memories are designed to perform multiple operations concurrently through different ports, manufacturing defects can cause one port to interfere with another port, affecting the data values that are read or written through either port. Other manufacturing defects can cause individual cells to interact unreliably. Memory defects are generally classified as cell faults, control faults, read/write logic faults, and interport faults.
Cell faults generally includes defects known as unlinked faults, coupling faults, linked faults, neighborhood pattern sensitive faults, and complex coupling faults. Unlinked faults represent faults that occur in specific cells, without regard to a particular port or to the values of nearby cells. Types of unlinked faults include stuck-at faults, in which a cell holds a particular data value permanently; transition faults, in which a cell cannot make a transition between two values; and data retention faults, in which a cell fails to retain the correct logic value after a period of time. Table I summarizes unlinked faults.
Coupling faults represent faults in which writing a value to one cell influences the data value of another cell. Coupling faults include inversion faults, in which inverting the value of a first cell inverts the value of a second cell; idempotent faults, in which inverting the value of a first cell causes a particular value (either a 1 or a 0) to be stored in a second cell; bridging faults, in which two cells are shorted together; state faults, in which a first cell is forced to a certain value if and only if a second cell holds a particular value; and disturbance faults, in which a first cell changes value in response to a read or write operation in a second cell. Bridging faults can behave as one of two types: AND-type or OR-type. In an AND-type fault, a first cell is forced to 0 if and only if a 0 is stored in second cell. In an OR-type fault, a first cell is forced to 1 if and only if a 1 is stored in a second cell. Table II summarizes coupling faults.
Other cell faults include linked faults, neighborhood pattern sensitive faults, and complex coupling faults. Linked faults comprise multiple coupling faults which occur when three or more cells interact to form faults. A first cell, for example, may affect the value of a second cell, which affects the value of a third cell. In another linked fault scenario, the first and third cells both affect the value of the second cell. The other previously discussed cell faults, by contrast, each occur between a single pair of cells. Neighborhood pattern sensitive faults typically appear as stuck-at, transition, or two-cell coupling faults, but only occur when nearby cells are in a particular state. Complex coupling are weak coupling faults that tend to occur only when multiple ports access the memory simultaneously. Table III summarizes these other cell faults.
Due to manufacturing defects such as short circuits and capacitive coupling between the ports, interport faults may occur when two or more ports access memory in parallel. Interport faults may be generally classified as word line shorts at the same row, word line shorts between adjacent rows, bit line shorts at the same column, and bit line shorts between adjacent columns. Word line shorts at the same row occur when activating a word line belonging to a first port causes the word line of a second port on the same row of memory cells to activate. Referring again to FIG. 1, if word line W10 (port 1, row 0) is shorted (or connected) to word line W20 (port 2, row 0), then activating word line W10 will activate word line W20 (and vice versa) if the short behaves as an OR-type short (as if the word lines were logically OR-ed), resulting in a word line short at the same row. If the short behaves as an AND-type short, however, then word line W10 can be activated only if word line W20 is activated at the same time, and vice versa (as if the word lines were logically AND-ed). Word line shorts between adjacent rows happen when a word line on one port affects the word line of a different port on an adjacent row. If word line W20 (port 2, row 0) is shorted to word line W11 (port 1, row 1), for example, then activating word line W11 causes word line W20 to activate if the short behaves as an OR-type short, resulting in a word line short between rows. Similarly, an AND-type short between word lines W11 and W20 will prevent either word line from being activated unless the other word line is also activated at the same time.
Bit line shorts at the same column occur when two bit lines on different ports, but in the same column, are connected. For example, a bit line short occurs if bit line B11 (port 1, column 1) connects to bit line B21 (port 2, column 1). The result of a short between bit line B11 and B21 is that when B21 is asserted, B11 is asserted (and vice versa). Bit line shorts between columns occur when the bit line of one port is shorted to the bit line of another port in an adjacent column. If asserting bit line B11 (port 1, column 1) asserts bit line B20 (port 2, column 0), then the resulting defect is known as a bit line short between columns. Table IV summarizes the basic types of interport faults.
FIG. 3A illustrates a word line fault in the FIFO of FIG. 2, using cells 200 and 210 as an example, at the first row of the memory array. As in FIG. 2, the write port comprises word line WW0 driving cell 200, word line WW1 driving cell 210, and bit line WB0 serving as the input signal for cells 200 and 210. Similarly, the read port comprises word line RW0 driving cell 200, word line RW1 driving cell 210, and bit line RB0 serving as the output signal for cells 200 and 210. Further, memory cell 200 holds a logic 0 value, and memory cell 210 holds a logic 1. As shown, a short 300 exists between word lines WW0 and RW0. If the short behaves as an OR-type short, then word line RW0 becomes activated when word line WW0 is activated, and word line WW0 becomes activated if word line RW0 becomes activated. In the example of FIG. 3A, a write operation is executed at cell 200, concurrently with a read operation of cell 210. Thus, the write port activates word line WW0 to access cell 200, and the read port activates word line RW1 to read the value of cell 210. Prior to the write operation, write bit line WB0 is driven to a logic 0 value. Cell 210 responds to the activation of word line RW1 by placing a logic 1 onto bit line RB0. If the short 300 behaves as an AND-type short, then the write word line WW0 will fail to pull high, however, and cell 200 will not receive the logic 0 value. If the fault behaves as an OR-type short, then both word lines WW0 and RW0 will pull high, and cell 200 will drive bit line RB0 with a logic 0, resulting in a bit line conflict with the logic 1 from cell 210. Depending on the nature of the memory technology, the read bit line RB0 may go to either the logic 0 or the logic 1.
FIG. 3B illustrates a word line fault between cells 200 and 210. FIG. 3B also depicts cell 220, at the third row of the array. As shown, memory cells 200, 210, and 220 each hold logic 0 values. A short 325 exists between word lines RW0 and WW1. If the short 325 behaves as an OR-type short, and if either word line RW0 or word line WW1 is activated, then the other word line becomes activated. If the short 325 behaves as an AND-type short, however, then neither word line RW0 nor WW1 can activate unless the other activates. In the example of FIG. 3B, a read operation is performed at cell 200 by activating word line RW0, and a concurrent write operation cell is performed at 220 by activating word line WW2. Prior to the write operation, bit line WB0 is driven with a logic 1 value. In response to activating word line WW2, cell 220 accepts the logic 1 value from bit line WW0. Because of short 325, word line RW0 will only activate if the short behave as an OR-type short. Accordingly, if short 325 behave as an AND-type short, the read operation will fail. If short 325 behaves as an OR-type short, then activating word line RW0 will cause word line WW1 to become activated. Accordingly, cell 210 will improperly receive the logic 1 value from bit line WW0.
Note that the short 325 occurs between the read word line of one cell and the write word line of the cell one address higher. Shorts which occur between a read word line and the write word line one address higher are known as type T1 word line shorts. In some cases, another type of short may occur between the read word line of a cell and the write word line of the cell one address lower. Shorts which occur between a read word line and a write word line in which the write word line is one address lower are known as type T2 word line shorts.
FIG. 3C illustrates a bit line fault at the same column, using cells 200 and 210 in the first column of the memory array. As shown, cells 200 and 210 hold logic 1 values. A write operation is performed at cell 200 by driving bit line WB0 to logic 0 and activating word line WW0. At the same time, a read operation is performed on cell 210 by activating word line RW1. Cell 200 thus receives the logic 0 value from bit line WB0, and cell 210 drives bit line RB0 with a logic 1 value. A short 350 exists between bit lines WB0 and RB0, however, resulting in either a read failure or a write failure. If the short 350 behaves as an OR-type short, then both bit lines RB0 and WB0 will carry a logic 1 value, and the write operation will fail. If the short 350 behaves as an AND-type short, then both bit lines RB0 and WB0 will carry a logic 0 value, and the read operation will return a logic 0 instead of a logic 1.
FIG. 3D illustrates a bit line fault between column 0 of the memory array, which comprises cells 200 and 210, and column 1 of the array, which includes cells 201 and 211. All four cells hold logic 0 values. In the example, a read operation is performed at row 0 of the array by activating word line RW0, causing cells 200 and 201 to drive bit lines RB0 and RB1, respectively, with logic 0 values. Similarly, a write operation is performed at row 1 of the array by activating word line WW1, causing cells 210 and 211 to accept values from bit lines WB0 and WB1, respectively. As shown, a short 375 exists between bit lines RB0 and WB1. Because bit line WB1 is driven with a logic 1 value for the write operation and cell 200 is driving bit line RB0 with a logic 0 value for the read operation, the short 375 will cause a data conflict. If the short 375 behaves as an OR-type short, then bit lines RB0 and WB1 will both carry logic 1 values, and the read operation will fail. If the short 375 behaves as an AND-type short, then bit lines RB0 and WB1 will both carry logic 0 values, and the write operation will fail.
In the examples of FIGS. 3A and 3C-D, the shorts 300, 350, and 375 resulted in conflicting values on the bit lines because some bit lines were driven with conflicting values. Note that if a read and write operation drive the same bit line with the same value (i.e., if a write operation and a read operation both place logic 0 onto a bit line), then a fault may not be apparent. For example, the short 300 between word lines WW0 and RW0 in FIG. 3A will not affect the values on bit lines WB0 and RB0 if cell 210 holds a logic 0 value or if the write operation at cell 200 stores a logic 1. A short that results in a bit line conflict will cause the bit line to carry either a 0 or 1 value, however, depending on whether the short behaves as an AND-type short or an OR-type short.
In addition to the faults listed above, FIFO""s are susceptible to faults known as control faults. Control faults generally include faults on the read and write enable lines, faults at the full flag and empty flag, and failure to execute the reset and retransmit commands. Faults in pointer-based FIFO""s also occur in the shift registers. Read/write faults can occur when the FIFO permits read and/or write operations, even when the associated read and write enable lines are deasserted. Other read/write faults occur when the FIFO is permanently disabled from reading and/or writing, regardless of the read and write enable line values.
Shift register faults can occur when the write shift register 232A and/or the read shift register 232B fail to properly manipulate the pointers. In some types of faults, a register bit is stuck at logic 0 or fails to store a logic 1. When pointer reaches the register bit, the pointer essentially vanishes, preventing the activation of any memory word on that port. Other types of faults cause a register bit to become stuck at 1 or fail to store a logic 0. Consequently, a logic 1 value is passed to the next register bit during each operation on that port, activating multiple memory words on that port. In some instances, the shift register may fail to shift altogether, keeping the pointer at the same memory word indefinitely.
Faults also may occur in the full flag and empty flag. One type of fault occurs if the full flag fails to set when the FIFO becomes full. Another type of fault occurs if the full flag is set when the FIFO is not full. Similarly, faults occur at the empty flag if the empty flag is set when the FIFO is not empty or if the empty flag fails to set when the FIFO becomes empty, such as after a reset command.
Certain other faults prevent proper execution of the reset and retransmit commands. A reset fault occurs when either the write pointer or read pointer (or both) fail to reset to address 0 in response to a reset command. A reset fault may also occur if a previous pointer bit fails to clear to logic 0. Similarly, a retransmit fault occurs when the read pointer fails to reset to address 0 in response to a retransmit command, or when address 0 sets to logic 1 but the previous pointer location fails to clear to logic 0.
Memory faults are unacceptable, so memory devices are thoroughly tested during the manufacturing process and discarded if any faults are detected. In the last few years, various techniques have been proposed for modeling and testing memory devices. Some of these techniques deal with random access memories, however, and do not apply to FIFO memory chips. Single port memories usually are tested using a technique called the March C algorithm, for example, or a variant of March C such as the March Cxe2x88x92, March C+, Smarch, or March LR algorithm.
The March C Algorithm includes six xe2x80x9cpasses,xe2x80x9d each of which addresses each memory cell individually. During Pass 1, March C writes a test pattern into the cells. The test pattern may be any desired sequence of bits, such as a xe2x80x9ccheckerboardxe2x80x9d pattern, but often comprises all 0""s. The 0 values can be written in any order, although the cells usually are addressed consecutively from address 0 to address Nxe2x88x921 or from address Nxe2x88x921 to address 0, where N represents the number of bits in the memory. Note also that N may represent the number of memory words, if desired, and the test may operate by addressing entire words instead of individual bits. Passes 2-5 also address each cell consecutively, executing two operations in sequence at each address. Passes 2 and 3 address the memory from address 0 to address Nxe2x88x921. During the first operation at each address in Pass 2, the test reads the current address to verify the value that was written during Pass 1. If the read operation does not return value that was written during Pass 1, then a fault is detected. The fault may have occurred either during the write operation of Pass 1 or the read operation of Pass 2 (or both). Next, the test inverts (or xe2x80x9ccomplementsxe2x80x9d) the data value of the current address. Thus, if the current cell holds a 0 value, then the test writes a 1 value to the cell, and vice versa. Similarly, the first operation of Pass 3 performs a read operation to verify the value written in Pass 2, and the second operation writes the inverted value to the cell. If the read operation returns a value different that the one written in Pass 2, then a fault is detected.
Passes 4-5 address the memory from cell Nxe2x88x921 to cell 0. The first operation in Pass 4 reads the current cell to verify the value that was written during Pass 3, and the second operation inverts the value through a write operation. Similarly, each iteration of Pass 5 first reads the value of the current cell to verify the value that was written during Pass 4 and then writes a complemented value to the cell. If the wrong value is read during any iteration of Pass 4 or Pass 5, then a fault is detected. Such a fault may have occurred during the read operation itself or during the previous write operation (or both). During Pass 6, the test reads each cell to verify the value that was written during Pass 5. As in Pass 1, the cells may be addressed in any order but preferably are accessed from address 0 to address Nxe2x88x921 or from address Nxe2x88x921 to address 0. If the wrong value is detected in any cell during Pass 6, a fault is detected. Table V summarizes the operations of the March C Algorithm in which the initial test pattern is zero for each cell.
Unfortunately, the March C algorithm cannot detect interport faults which occur in multiport memories, including FIFO""s. Though alternative techniques have been developed to detect interport faults, most of these techniques fail to detect all of the possible interport faults. Other techniques require modifications to the memory device. Such modifications, however, may be prohibitively expensive to mass produce or may prove incompatible with the needs of the is end user. Still other techniques require a large number of tests, and thus extensive testing time, unless detailed structural information about the memory is known. Although some techniques have been developed to effectively test interport faults, many of these tests cover only interport faults, failing to detect other types of faults. Other techniques which cover interport faults make the assumption that all ports are read/write ports, so faults that occur between read-only ports and between write-only ports are not detected. In addition, some of these tests require random access addressing, which cannot be executed on a FIFO. Further, these tests fail to detect FIFO-specific faults, such as faults in the full and empty flags, faults in the shift registers, and reset/retransmit faults.
Control faults in FIFO""s can be particularly difficult to track, since many signals involved in implementing the control operations cannot be directly observed. The values of the full and empty flags, for example, typically cannot be read from the memory. Although the read and write enable lines are input to the memory and can therefore be observed, it is difficult to determine whether asserting and deasserting the enable lines successfully activate memory locations. Similarly, FIFO""s do not permit the values of the read and write shift registers to be read out, and without directly observing the shift register values it is difficult to verify operation of the reset and retransmit commands.
For the foregoing reasons, an efficient and reliable technique for detecting memory faults in FIFO memories, including dual port FIFO""s, would greatly improve the manufacturing and testing of memories. Such a technique, if devised, should cover all possible faults which occur in FIFO""s, including control faults which are specific to FIFO""s, as well as faults common to conventional memories, such as interport faults and faults that occur in single port memories, without requiring excessive testing time. Further, the technique should apply to any type of memory design without requiring modifications to the cell architecture and should cover both read and write ports. In addition, without actually having to observe internal values in the FIFO, the test should uncover control faults which normally would require observing the values. Despite the apparent advantages that such a technique would provide, no device or method provides these features.
Accordingly, the present invention discloses an efficient and reliable technique for detecting faults which occur in FIFO""s, including control faults which are specific to FIFO""s, as well as faults common to conventional memories, such as interport faults and faults that occur in single port memories. Further, the faults are detected without directly observing internal values within the FIFO, such as the full and empty flag values and the shift register values.
In accordance with a preferred embodiment, an Interport FIFO Test that detects interport faults in a FIFO comprises 14 test stages, including 5 write passes and 4 read passes. In order to expose interport faults, the interport test executes read and write operations in which the read operations and write operations occur at different addresses. Because FIFO""s do not accept read and write addresses, the address offset is accomplished by executing the read and write operations in a particular order.
A first portion of the test comprises executing a plurality of write operations until the write pointer reaches a first predetermined position relative to the read pointer. Next, the test performs a plurality of concurrent read and write operations. In a preferred embodiment, the first predetermined position is calculated to place the write pointer 2 addresses behind the read pointer (or Nxe2x88x922 addresses ahead of the read pointer) during the concurrent operations. The concurrent operations are executed in multiple passes through the memory, and the test write values are inverted before each new pass so that the test detects interport faults and cell faults. By executing concurrent operations, interport faults are activated and detected by the read operations. A second portion of the test comprises performing a plurality of write operations until the write pointer reaches a second predetermined position relative to the read pointer, and the test then performs concurrent read and write operations, maintaining the read and write pointer at a fixed number of addresses apart. The second portion of the test also preferably includes multiple passes, with the write test data inverted for each pass to activate cell faults. In a preferred embodiment, the second predetermined position is calculated to place the write pointer 1 address behind the read pointer (or Nxe2x88x921 addresses ahead of the read pointer) during the concurrent operations. Note that the test may comprise only the first portion or only the second portion if the memory layout is known. If the memory layout is not known, then the test preferably includes both portions.
In another preferred test embodiment, a flag test that detects faults in the full and empty flags comprises 8 test stages. In order to expose faults in the full and empty flags, the flag test attempts to execute write operations when the full flag is set and to execute read operations when the empty flag is set. If the FIFO executes an attempted operation, then a fault is detected. To positively identify that the FIFO has executed an attempted operation, the test writes two different test values into two different memory locations. The flag test reads a single memory location determine whether or not the FIFO executed a read or write operation.
The full and empty flag test comprises first resetting the read and write pointers and then writing test values to the memory until the memory is full, a condition which should trigger the full flag. The last value written to the memory equals the complement of the value written to the first memory location. Next, another write operation is attempted at the first memory location, using the complement of the value previously written to the first memory location, and then a read operation is performed. If the full flag fails to prevent the attempted write operation, then the read operation will return the complemented test value. Thus, a fault is declared unless the read operation returns the test value. Next, a series of read operations is performed through the last memory location. Thus, the empty flag should set, preventing further read operations. Nevertheless, an additional read operation is attempted. If the FIFO executes the attempted read operation, the read value will be the test value written to the first memory location. If the FIFO does not execute the attempted read operation, then the FIFO will either tristate its read lines or return the value written to the last memory location, which equals the complement of the value written to the first memory location. Thus, the flag test is implemented using only a single memory by manipulating the test values used for the write operations.
In another preferred embodiment, an enable line test detects faults in the read and write enable lines by attempting read operations with the read enable line deasserted, attempting write operations with the write enable line deasserted, and then determining whether the FIFO executed the attempted operations. The enable line test first initiates two write operations, the first operation with the write enable asserted, and the second operation with the write enable line deasserted. The second write operation writes the complement of the value used for the first write operation. A first read operation, which preferably is executed concurrently with the second write operation, verifies the value written during the first write operation. A second read operation then is attempted. If deasserting the write enable line successfully prevented the second write operation, then the empty flag will be set after the first read, thus preventing the second read. Thus, if the second read operation returns the test value from the second write attempt, a fault is detected in the write enable line. Next, a third write operation is performed with the write enable line asserted, with the same test write value used for the second write operation, and the read pointer is relocated through a retransmit command. After relocating the read pointer, a third and a fourth read operation are performed. The third read operation is attempted with the read enable deasserted, and the fourth read operation is executed with the read enable asserted. If the FIFO does not execute the first read operation, then the second read operation will return the value of the first write operation. If the FIFO does execute the first read operation, however, then the second read operation will return the value of the second write operation, which is the complement of the first write operation. Thus, the enable line test detects faults in the enable lines by verifying that read and write operations cannot occur with the read and write enable lines deasserted.
A preferred embodiment of a reset and retransmit test activates and detects faults in the reset and retransmit operations. Because the reset and retransmit operations may occur when the pointers are at any locations within the memory, the reset and retransmit test tests each memory address individually. First, the reset and retransmit test initializes the array and verifies that the write pointer will reset from address 1. To test the write pointer at address 1, the test performs a first write operation at address 0, followed by a reset command, a second write operation, and then a read operation. The first write operation complements the data written to the array during initialization. The second write operation complements the data at address 0 written during the first write operation. If the read operation returns the test value written during the first write operation, then the reset operation must have failed. The reset command is verified only if the read operation returns the test value written during the second operation.
Next, the reset and retransmit executes a procedure to test the reset and retransmit commands for the remaining addresses. A preferred embodiment discloses a test procedure that is executed repeatedly to test the remaining addresses 1 to Nxe2x88x921. When testing the Kth address, the reset and retransmit test first resets the read and write pointers to address 0. Next, the test writes a series of test values to memory addresses 0 through K and performs a series of read operations on memory addresses 0 to K. In a preferred embodiment, the read operations at addresses 0 through Kxe2x88x921 occur concurrently with the write operations at addresses 1 through K, in order to expedite the test. Also, the test value written to the first address represents the complement of the test value written to address K. Following the read and write operations, the read pointer is located at address K, and the write pointer is located at address K+1. A retransmit command then is executed to relocate the read pointer to address 0, and another series of read operations is performed to verify the values in addresses 0 to Kxe2x88x921. If the read pointer fails to relocate, the read operations will detect the fault.
Next, the read and write pointers are reset to address 0, and the test executes two write operations at addresses 0 and 1, followed by two read operations to verify the write operations at addresses 0 and 1. In a preferred embodiment, the read operation at address 0 occurs concurrently with the write operation at address 1. The write operation at address 0 stores the same test value used to initialize the memory at the beginning of the test, but the write operation at address 1 stores the complement of the initialization value. Because the two read operations return complementary values, faults in the reset command can be detected. Accordingly, the reset and retransmit test verifies the operation of the reset and retransmit operations at any given address, using only read, write, reset, and retransmit operations and thus avoiding the need to observe internal values within the FIFO.
A memory tester capable of implementing the FIFO fault test comprises control circuitry capable of accessing a FIFO and managing the test operations. Accordingly, a control logic device manages the test operations by driving control lines to the FIFO (including write enable, reset, retransmit, write enable, and any other control line), by transmitting write data to the FIFO, and by receiving and evaluating read data from the FIFO. The memory test includes a write register that receives write values from the control logic and places the write value onto a write bus attached to the FIFO. Accordingly, the FIFO accepts the value of the write register during write operations. Similarly, the memory test includes a read register that receives read values from the FIFO. The control logic is thus capable of determining the read value by examining the read register. In addition, the memory tester includes a comparator capable of comparing the read register value with a predetermined expected value. The expected value represents the value expected to be returned from a read operation. Thus, the control logic supplies the expected value to the comparator, which asserts a match signal if the expected value matches the contents of the read register. Accordingly, the control logic is capable of performing read and write operations to the FIFO and determining whether read operations return the values expected, as described in the memory tests.
Thus, the present invention comprises a combination of features and advantages that enable it to substantially advance the art by providing a method and apparatus for testing faults in FIFO memories. These and various other characteristics and advantages of the present invention will be readily apparent to those skilled in the art upon reading the following detailed description of the preferred embodiments of the invention and by referring to the accompanying drawings.